README.md

287. Find the Duplicate Number

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Example 1:

Input: [1,3,4,2,2] Output: 2 

Example 2:

Input: [3,1,3,4,2] Output: 3 

Note:

1. You must not modify the array (assume the array is read only).
2. You must use only constant, O(1) extra space.
3. Your runtime complexity should be less than O(n²).
4. There is only one duplicate number in the array, but it could be repeated more than once.

Solutions (Rust)

1. Two Pointers

implSolution{pubfnfind_duplicate(nums:Vec<i32>) -> i32{letmut p1 = 0;letmut p2 = 0;loop{ p1 = nums[p1 asusize]; p2 = nums[nums[p2 asusize]asusize];if p1 == p2 {break;}} p1 = 0;while p1 != p2 { p1 = nums[p1 asusize]; p2 = nums[p2 asusize];} p1 }}